package com.interview.javabase.algorithm.动态规划;

/**
 * @author www.byteblogs.com
 * @date 2021-10-09
 * @since 2.0
 */
public class 最大回文子串 {

    public static void main(String[] args) {
        int i = longestPalindSubsequence("aaecdaa");
        System.out.println(i);
    }

    public static int longestPalindSubsequence(String s) {

        int n = s.length();
        char[] c = s.toCharArray();

        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (c[i] == c[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[0][n - 1];
    }
}
